Course contents: Rudiments of Mathematical Logic & Set Theory: propositional logic, elements of first-order logic, the algebra of sets, finite and infinite sets, cardinality and Cantor’s diagonal methods. Proof methods: mathematical induction (strong induction and wellordering principle), diagonalization, reductio ad absurdum. Relations and Functions: Cartesian product, binary and n-ary relations, functions, lattices and partial orders, equivalence and congruence relations. Combinatorics: rules of sum and product, combinations and permutations (with/without repetition), balls in urns, inclusion/exclusion principle, pigeonhole principle. Rudiments of Graph Theory: graph species, Euler & Hamilton graphs and trails, planar graphs, graph coloring, matching theorems, elements of Ramsey Theory. Trees: trees and rooted trees, applications, Huffman codes. Depending on the progress, number theory and the basics of algorithm analysis can be touched upon.

At the end of the course the student will be able to:

• recognize and employ fundamental mathematical notions (sets, functions, relations, etc,) for defining and solving computational problems
• understand complex combinatorial problems and employ the combinatorial strategies introduced in the course
• understand problems in Graph Theory and devise solving strategies and techniques
• state and analyze correct proofs, using the fundamental techniques reviewed in the course (mathematical induction, reductio ad absurdum, etc.)
• understand and solve problems in elementary Number Theory and its applications

Assessment: Written exams (70%) at the end of the semester and exercises (30%), where the weights may be changed by ±10%.